package com.wang;

import java.util.HashSet;
import java.util.Set;

public class MainJava {
    public static final String accessToken = "80e5a0c7-573a-4812-886f-11cfefe11d18";

    public static void dp4(String[] args) {
        String s1 = "intention";
        String s2 = "execution";
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        dp[0][0] = s1.charAt(0) == s2.charAt(0) ? 0 : 1;

        dp[0][0] = 0;
        for (int i = 1; i < s1.length() + 1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < s2.length() + 1; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i < s1.length() + 1; i++) {
            for (int j = 1; j < s2.length() + 1; j++) {
                // 增加
                int n1 = dp[i][j-1] + 1;
                // 删除
                int n2 = dp[i-1][j] + 1;
                // 替换
                int n3 = dp[i - 1][j - 1] + (s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1);
                int n = Math.min(n1, Math.min(n2, n3));
                dp[i][j] = n;
            }
        }
        printDp(dp);

    }

    public static void dp3(String[] args) {
        String s = "catsandog";
        String[] as = new String[]{"cats", "dog", "sand", "and", "cat"};
        Set<String> set = new HashSet<>(as.length);
        int max = 0;
        for (String a : as) {
            max = a.length() > max ? a.length() : max;
            set.add(a);
        }

        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j <= max && i - j >= 0; j++) {
                String ss = s.substring(i - j, i);
                if (dp[i - j] == 1 && set.contains(ss)) {
                    dp[i] = 1;
                }
            }
        }
        printDp(new int[][]{dp});
    }

    public static void dp2(String[] args) {
        int[][] as = new int[][]{
                new int[]{1, 3, 1},
                new int[]{1, 5, 1},
                new int[]{4, 2, 1}
        };

        int[][] dp = new int[as.length + 1][as[0].length + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp.length; j++) {
                if (i == 1 && j == 1) {
                    dp[1][1] = as[0][0];
                    continue;
                }

                int min = Math.min(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = min + as[i - 1][j - 1];
            }
        }
        printDp(dp);
    }

    public static void dp1(String[] args) {
        int[][] as = new int[][]{
                new int[4],
                new int[]{0, 1, 1, 0},
                new int[4],
                new int[4]
        };

        int[][] dp = new int[as.length + 1][as[0].length + 1];
        dp[0][1] = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp.length; j++) {
                if (as[i - 1][j - 1] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        printDp(dp);
    }

    public static void dp(String[] args) throws Exception {
        String s1 = "hellooooworld";
        String s2 = "aloop";
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        int[] max = new int[]{0, 0};
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                if (dp[i][j] > dp[max[0]][max[1]]) {
                    max[0] = i;
                    max[1] = j;
                }
            }
        }
        printDp(dp);
        System.out.println(dp[max[0]][max[1]]);
        System.out.println(s1.substring(max[0] - dp[max[0]][max[1]], max[0]));
    }

    public static void printDp(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            for (int k = 0; k < dp[i].length; k++) {
                System.out.print(dp[i][k] + " ");
            }
            System.out.println();
        }
    }
}
